package com.chimm.main;

import java.util.Arrays;

/**
 * 插入排序有3种：
 * 1. 直接插入排序 （基于顺序查找定位）
 * 2. 折半插入排序 （基于折半查找定位）
 * 3. 希尔排序     （基于逐趟缩小增量）
 * <p>
 * <p>
 * 1. 直接插入排序
 * 排序过程：
 * 整个排序过程循环n-1次，将第一个数看作有序序列，从第二个记录开始，逐个进行插入，直至整个序列有序。
 *
 *
 * 分析：用直接插入排序，数据序列越接近有序，比较次数越少
 */
public class InsertSort {


    public static void main(String[] args) {

        int[] a = {32, 43, 23, 13, 5}; //定义无序数组

        int length = a.length; //数组长度

        int insertNum; //将要插入的数

        for (int i = 1; i < length; i++) { //循环的次数

            insertNum = a[i]; //要插入的数
            int j = i - 1; //已经排好序的序列元素个数

                while (j >= 0 && a[j] > insertNum) {
                //序列从后向前循环，将大于insertNum的数向后移动一格
                a[j + 1] = a[j];
                j--;
            }

            a[j + 1] = insertNum;
            System.out.println(Arrays.toString(a));
        }




    }
}
